package ali;

/**
 * @author keboom
 * @date 2021/4/27 20:06
 *
 * 左神的硬币问题，给多个金额的硬币，凑出一个数字的要是用的最少硬币数。
 */
public class Test2 {
    public int minCoins1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        return process(arr, 0, aim);
    }

    private int process(int[] arr, int index, int aim) {
        if (index == arr.length) {
            return aim == 0 ? 0 : -1;
        }
        int res = -1;
        for (int k = 0; k * arr[index] <= aim; k++) {
            int next = process(arr, index + 1, aim - k * arr[index]);
            if (next != -1) {
                res = res == -1 ? next + k : Math.min(res, next + k);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        int[] arr = {5, 2, 3};
        System.out.println(test2.minCoins1(arr, 20));
    }
}
